{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grover algorithm\n",
    "\n",
    "The Grover algorithm is widely used for unstructured search challenges. In this case it will be used find the right values of variables within a mathematical expression.\n",
    "\n",
    "First, we will use the Classiq build-in Gover algorithm, to show how easy it can be to create a Grover algorithm with Classiq. Next, you will create your own implementation from scratch."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:22.804225Z",
     "iopub.status.busy": "2024-05-07T14:27:22.803774Z",
     "iopub.status.idle": "2024-05-07T14:27:28.482034Z",
     "shell.execute_reply": "2024-05-07T14:27:28.481347Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/1e2b44ea-7338-41d3-885d-0736e4e8e159?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import *\n",
    "\n",
    "grover_model = construct_grover_model(\n",
    "    definitions=[\n",
    "        (\"a\", RegisterUserInput(size=4)),\n",
    "        (\"b\", RegisterUserInput(size=4)),\n",
    "    ],\n",
    "    expression=\"2 * a == b\",\n",
    ")\n",
    "qprog = synthesize(grover_model)\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Let's build our naive implementation of grover\n",
    "\n",
    "We are going to create a Grover algorithm that will find integer values that solve this equation: `2 * a = b`.\n",
    "\n",
    "This is the circuit that we want to create:\n",
    "<img src=\"\" />\n",
    "\n",
    "\n",
    "The goal is to create this circuit in the Classiq SDK. This implementation will not utilize all possible functions of the Classiq    SDK for learning purposes.\n",
    "\n",
    "These are the steps we will follow\n",
    "\n",
    "1. Create two-qubit arrays that will hold the values of the solution - will be done in step 5\n",
    "2. Place the qubits in an equal superposition\n",
    "3. Create the Grover Oracle\n",
    "4. Create the Grover Diffuser\n",
    "5. Bring everything together\n",
    "6. Execute the circuit\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Create a Hadamard transform function\n",
    "Fill out the function below that will apply an H gate on each of the qubits that are passed to the function.\n",
    "Use the `repeat` function to apply the H gate to all the qubits. \n",
    "\n",
    "Here are some helpful: [Code examples](#Helpfull-code-examples)\n",
    "\n",
    "<details>\n",
    "<summary>If you do not have enough time click here for a shortcut</summary>\n",
    "\n",
    "You can use the build in the `hadamard_transform(q: qbit[])`\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:28.566887Z",
     "iopub.status.busy": "2024-05-07T14:27:28.566161Z",
     "iopub.status.idle": "2024-05-07T14:27:28.573816Z",
     "shell.execute_reply": "2024-05-07T14:27:28.573162Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import *\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_hadamard_transform(reg: QArray[QBit]):\n",
    "    # Your code\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Create the Grover Oracle\n",
    "\n",
    "The Grover oracle will encode the arithmetic expression into the quantum circuit. We will use an in-place-xor to implement the quantum predicate, you do not have to manually do this. The part of the algorithm that we will create is seen in the image here:\n",
    "\n",
    "<img src=\"\" />\n",
    "\n",
    "Here are some helpful: [Code examples](#Helpfull-code-examples)\n",
    "\n",
    "In the `prepare_minus` function\n",
    "1. Add gates to the input qubit to prepare a minus state.\n",
    "\n",
    "In the `my_oracle` function\n",
    "1. Create and allocate a qubit named `aux`\n",
    "2. Use `within_apply` to first compute the minus state, then as an action apply `my_predicate`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:28.578655Z",
     "iopub.status.busy": "2024-05-07T14:27:28.578001Z",
     "iopub.status.idle": "2024-05-07T14:27:28.586949Z",
     "shell.execute_reply": "2024-05-07T14:27:28.586256Z"
    }
   },
   "outputs": [],
   "source": [
    "@qfunc\n",
    "def my_predicate(res: QNum, a: QNum, b: QNum) -> None:\n",
    "    res ^= 2 * a == b * a\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def prepare_minus(aux: QBit):\n",
    "    # Your code here\n",
    "    pass\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_oracle(a: QNum, b: QNum):\n",
    "    # Your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Create the Grover Diffuser\n",
    "\n",
    "The Grover diffuser is an important part of the Grover Algorithm. Below is an image of how the diffuser looks. On the left, you see the input `a` and `b` registers.\n",
    "\n",
    "<img src=\"\" />\n",
    "\n",
    "Here are some helpful: [Code examples](#Helpfull-code-examples)\n",
    "\n",
    "This function should have these steps:\n",
    "1. Apply the state prep (All `H` gates) to the input registers\n",
    "2. Apply `X` gates to all inputs\n",
    "3. Apply a controlled `Z` gate on the last qubit of the input qubits. The controlled part should be all the other qubits passed to the function\n",
    "4. Apply the invert of state preparation (All `H` gates), on the registers\n",
    "\n",
    "<details>\n",
    "<summary>\n",
    "Detailed instructions\n",
    "</summary>\n",
    "\n",
    "1. Create a new register called `reg` of type `QArray`\n",
    "2. Create a temporary `QArray` register called `msbs` and a temporary `QBit` called `lsb`; no need to allocate them yet.\n",
    "2. Join the `a` and `b` input into the new `reg` using the `bind()` function\n",
    "3. Apply the inverse of `my_hadamard_transform()` to the register\n",
    "4. Apply the `X` gate to each of the qubits in the register using the `apply_to_all()` function\n",
    "5. Split the `reg` into `msbs` and `lsb`, you will allocate n-1 qubits to `msbs` and the other to `lsb`\n",
    "6. Create a control function, this takes two named parameters:\n",
    "    - `ctrl` this will take the `msbs` \n",
    "    - `operand` this will take an anonymous function which a `Z` operation on the `lsb` qbit\n",
    "7. join the `msbs` and `lsb` together in the `reg`\n",
    "8. Apply the invert of the `my_hadamard_transform()` on the register using the `invert()` function\n",
    "9. split the register back into `a` and `b` using the `bind()` function.\n",
    "\n",
    "</details>\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:28.590488Z",
     "iopub.status.busy": "2024-05-07T14:27:28.590011Z",
     "iopub.status.idle": "2024-05-07T14:27:28.598112Z",
     "shell.execute_reply": "2024-05-07T14:27:28.597286Z"
    }
   },
   "outputs": [],
   "source": [
    "@qfunc\n",
    "def my_diffuser(a: QNum, b: QNum):\n",
    "    # Your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Brining everything together\n",
    "\n",
    "1. Allocate 4 qubits into the `a` and `b` variable\n",
    "2. apply your `my_hadamard_transform()` on both `a` and `b`\n",
    "3. apply `my_oracle()` on `a` and `b`\n",
    "4. apply `my_diffuser()` on `a` and `b`\n",
    "5. synthesize the model and execute in the Ide"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:28.601753Z",
     "iopub.status.busy": "2024-05-07T14:27:28.601276Z",
     "iopub.status.idle": "2024-05-07T14:27:29.827035Z",
     "shell.execute_reply": "2024-05-07T14:27:29.826319Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/d995422b-118a-4915-8ba3-8d25ce05633e?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "@qfunc\n",
    "def main(\n",
    "    # a: Output[QNum],\n",
    "    # b: Output[QNum]\n",
    ") -> None:\n",
    "    #     #Your code here\n",
    "    pass\n",
    "\n",
    "\n",
    "model = create_model(main)\n",
    "qprog = synthesize(model)\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. Execute the ciruit\n",
    "\n",
    "1. When the circuit opens in the IDE, press \"Execute\". \n",
    "2. Pick the AER simulator from the \"Classiq\" provider.\n",
    "3. Execute the job.\n",
    "4. Validate the results.\n",
    "<details>\n",
    "<summary>\n",
    "The result should look something like this:\n",
    "</summary>\n",
    "\n",
    "<img src=\"\" />\n",
    "\n",
    "</details>\n",
    "\n",
    "As you can see there are various, right answers to the equation. When you hover over the high count bars you see the integer results from that specific shot.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7. Hardware aware synthesis\n",
    "\n",
    "With the Classiq synthesis engine we can create optimized quantum circuits for each quantum computer. Let's synthesize specifically for IONQ Aria and IBM Cairo to see the difference in implementation of the model that you created. [Here](https://docs.classiq.io/latest/reference-manual/platform/synthesis/hardware-aware-synthesis/) is the documentation for the hardware aware synthesis. Please compare the different circuits when you synthesize for two providers.\n",
    "\n",
    "1. `backend_service_provider=\"IBM Quantum\", backend_name=\"ibm_torino\"`\n",
    "2. `backend_service_provider=\"Azure Quantum\", backend_name=\"ionq.qpu.aria-1\"`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:29.829928Z",
     "iopub.status.busy": "2024-05-07T14:27:29.829354Z",
     "iopub.status.idle": "2024-05-07T14:27:29.832631Z",
     "shell.execute_reply": "2024-05-07T14:27:29.832062Z"
    }
   },
   "outputs": [],
   "source": [
    "# Your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8. Optimize the circuit using Classiq optimization\n",
    "\n",
    "#### Minimize number of qubits\n",
    "\n",
    "When you have created your model, the Classiq synthesis engine can create a logical circuit from that model. We can steer the engine to optimize the circuit for specific preferences. \n",
    "\n",
    "\n",
    "Firstly, let's look at the statistics of the created circuit above. \n",
    "\n",
    "```\n",
    "circuit_detail = GeneratedCircuit.from_qprog(qprog)\n",
    "\n",
    "print(circuit_detail.data.width)\n",
    "```\n",
    "This shows that the circuit uses **11** qubits. Let's see if we can reduce that number by instructing the synthesis engine to optimize for a minimal number of qubits.\n",
    "\n",
    "Before the `synthesize()` call, you can steer the Synthesis engine to optimize for a specific parameter. Use the `set_constraints(model, Constraints(...))` function to steer the synthesis engine to minimize the use of qubits. Now synthesize the circuit with the new constriants.\n",
    "\n",
    "Validate that he created circuit only uses **10** qubits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:29.834923Z",
     "iopub.status.busy": "2024-05-07T14:27:29.834649Z",
     "iopub.status.idle": "2024-05-07T14:27:29.837374Z",
     "shell.execute_reply": "2024-05-07T14:27:29.836783Z"
    }
   },
   "outputs": [],
   "source": [
    "# Your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9. Multiple Grover calls\n",
    "\n",
    "In the Grover algorithm, you might want to apply the Grover oracle and diffuser multiple times when you have more variables/ more qubits.\n",
    "\n",
    "Create it in multiple steps:\n",
    "\n",
    "1. Create a new `qfunc` called `my_grover_search(a: QNum, b: QNum)`\n",
    "2. Add the `my_oracle()` and `my_diffuser()` to the new function\n",
    "3. In the main function, add a `repeat()` that will call the newly created function 2 times\n",
    "4. validate everything works by executing the algorithm again in the IDE\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:29.839816Z",
     "iopub.status.busy": "2024-05-07T14:27:29.839391Z",
     "iopub.status.idle": "2024-05-07T14:27:31.038974Z",
     "shell.execute_reply": "2024-05-07T14:27:31.037641Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/1bd52eae-633b-4c5c-a26e-1706e6e3b3a4?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "@qfunc\n",
    "def main(\n",
    "    # a: Output[QNum],\n",
    "    # b: Output[QNum]\n",
    "):\n",
    "    # Your code here\n",
    "    pass\n",
    "\n",
    "\n",
    "model = create_model(main)\n",
    "qprog = synthesize(model)\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10. Execute using Python\n",
    "\n",
    "You might want to use the results from your quantum circuit in a later step of a larger program. In order to do so you might want to execute in Python, to get the results back in your quantum program. [Here](https://docs.classiq.io/latest/classiq_101/classiq_concepts/execute/) is the documentation for Execution.\n",
    "\n",
    "Execute the program using the `Execute()` function and check the counts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:31.043693Z",
     "iopub.status.busy": "2024-05-07T14:27:31.042518Z",
     "iopub.status.idle": "2024-05-07T14:27:31.047799Z",
     "shell.execute_reply": "2024-05-07T14:27:31.047115Z"
    }
   },
   "outputs": [],
   "source": [
    "# Your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Helpfull code examples\n",
    "\n",
    "Create and allocate a variable, in this example allocate a single qubit into the zero state - possible variable types `QBit`, `QNum`, `QArray`\n",
    "- ```\n",
    "   foo = QBit('YOUR_QUBIT_NAME')\n",
    "   allocate(1,foo)\n",
    "   ```\n",
    "\n",
    "Concatenate two Qubit registers\n",
    "- ```\n",
    "   new_reg = QArray('NEW_REG')\n",
    "   bar = bind([foo, bar], new_reg)\n",
    "   ```\n",
    "\n",
    "Split a quantum register into two quantum registers. Let's assume there is a quantum register named `reg` with 8 qubits that you want to split into two separate registers of 4 qubits each\n",
    "- ```\n",
    "   foo = QArray(\"foo\")\n",
    "   bar = QArry(\"bar\")\n",
    "   bind(reg,[foo,bar])\n",
    "   ```\n",
    "\n",
    "Apply a gate to all qubits in a register, in this example apply the X gate to all qubits.\n",
    "- ```\n",
    "   apply_to_all(X, reg)\n",
    "   ```\n",
    "\n",
    "Apply an X gate to a qubit\n",
    "- ```\n",
    "   X(reg)\n",
    "   ```\n",
    "\n",
    "Apply an invert operation to a qubit\n",
    "- ```\n",
    "   invert(lamda: X(reg))\n",
    "   ```\n",
    "\n",
    "Apply a controlled operation to a qubit\n",
    "- ```\n",
    "   control(\n",
    "        operand=lambda: X(qubit),\n",
    "        ctrl=reg,\n",
    "    )\n",
    "   ```\n",
    "\n",
    "Apply an operation to each qubit in an array\n",
    "- ```\n",
    "   repeat(\n",
    "    count= CInt,\n",
    "    iteration= QCallable[CInt],\n",
    "   )\n",
    "   ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The full solution for your reference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:31.052406Z",
     "iopub.status.busy": "2024-05-07T14:27:31.051325Z",
     "iopub.status.idle": "2024-05-07T14:27:34.553694Z",
     "shell.execute_reply": "2024-05-07T14:27:34.552980Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/79b131ad-8ad1-4671-916c-661cf568bb43?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "@qfunc\n",
    "def my_hadamard_transform(reg: QArray[QBit]):\n",
    "    repeat(count=reg.len, iteration=lambda index: H(reg[index]))\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_predicate(res: QNum, a: QNum, b: QNum) -> None:\n",
    "    res ^= 2 * a == b\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def prepare_minus(aux: QBit):\n",
    "    X(aux)\n",
    "    H(aux)\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_oracle(a: QNum, b: QNum):\n",
    "    aux = QBit(\"aux\")\n",
    "    allocate(1, aux)\n",
    "\n",
    "    within_apply(\n",
    "        compute=lambda: prepare_minus(aux),\n",
    "        action=lambda: my_predicate(res=aux, a=a, b=b),\n",
    "    )\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_diffuser(a: QNum, b: QNum):\n",
    "    reg = QArray(\"reg\")\n",
    "    msbs = QArray(\"msbs\")\n",
    "    lsb = QBit(\"lsb\")\n",
    "    bind([a, b], reg)\n",
    "    my_hadamard_transform(reg)\n",
    "    apply_to_all(gate_operand=X, target=reg)\n",
    "    bind(reg, [msbs, lsb])\n",
    "    control(ctrl=msbs, operand=lambda: Z(lsb))\n",
    "    bind([msbs, lsb], reg)\n",
    "    invert(operand=lambda: my_hadamard_transform(reg))\n",
    "    bind(reg, [a, b])\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(a: Output[QNum], b: Output[QNum]) -> None:\n",
    "\n",
    "    allocate(4, a)\n",
    "    allocate(4, b)\n",
    "    my_hadamard_transform(a)\n",
    "    my_hadamard_transform(b)\n",
    "    my_oracle(a, b)\n",
    "    my_diffuser(a, b)\n",
    "\n",
    "\n",
    "model = create_model(main)\n",
    "qprog = synthesize(model)\n",
    "show(qprog)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
